수학적 프레임워크
핵심 목표는 벡터 $x \in \mathbb{R}^n$를 찾아, 선형 조합 $Ax = x_1a_1 + \dots + x_na_n$가 $b$를 가장 잘 근사하게 만드는 것입니다. 이는 일반적으로 $b$를 회귀 변수(행렬 $A$의 열들)에 대한 회귀 (행렬 $A$의 열들)로 표현됩니다.
우리는 잔여 벡터 $r = Ax - b$에 주목합니다. 실제로는 과잉 결정 시스템 여기서 $m > n$입니다. 왜냐하면 $m = n$이고 $A$가 비특이일 경우 최적 해는 단순히 $A^{-1}b$이며, 오차는 0이 되기 때문입니다. 이는 최적화 문제에서는 당연한 사례입니다.
표준 변형
오차의 '맛'(즉, 어떤 종류의 오차를 처벌하고 싶은지)에 따라 다른 노름을 선택합니다:
가장 일반적인 방법입니다. 잔여 오차의 제곱합을 최소화합니다: $\|Ax - b\|_2^2$. 큰 이상치에 민감하지만, 정규 방정식을 통해 해석적 해를 제공합니다.
최대 절댓값 잔여 오차 $\max_i |r_i|$를 최소화합니다. 모든 측정값이 엄격한 허용 오차 내에 있어야 하는 경우에 사용됩니다. 다음 선형 계획법(LP)으로 해결할 수 있습니다: 최대값 절댓값 잔여 오차 $\max_i |r_i|$입니다. 모든 측정값이 엄격한 허용 오차 내에 있어야 할 때 사용됩니다. 다음 선형 계획법(LP)으로 해결할 수 있습니다:
최소화: $t$
제약조건: $-t\mathbf{1} \preceq Ax - b \preceq t\mathbf{1}$
모든 잔여 오차의 절댓값의 합 $\sum |r_i|$를 최소화합니다. 오차를 제곱하지 않기 때문에 이상치에 강건합니다. 또한 선형 계획법으로도 해결할 수 있습니다:
최소화: $\mathbf{1}^T t$
제약조건: $-t \preceq Ax - b \preceq t$
추정 맥락
많은 공학 분야에서 진짜 상태 $x$는 노이즈에 의해 왜곡된다고 가정합니다: $y = Ax + v$. 우리의 목적은 추정값 $\hat{x} = \text{argmin}_z \|Az - y\|$를 찾는 것입니다. 노름을 선택함으로써, 우리는 노이즈 $v$의 통계적 분포에 대해 가정을 하고 있는 것입니다.